\documentclass{article}
\usepackage{graphicx}
\setlength{\pdfpagewidth}{\paperwidth}
\setlength{\pdfpageheight}{\paperheight} 

\begin{document}
  \noindent CS 341 \hfill Cell Phone Tower Placement \\
  Travis Raines, Conrad Dean \hfill \today \\
	\section{Modified files}
		No files were modified. Any functions I used that were not included with deap are in {\textit ga\_towers.py}.
	\section{Algorithm}
		\subsection{Representation}
			The towers were represented as list of thirty float coordinate pairs.
		\subsection{Mutation}
			$k$ was chosen from a Gaussian distribution with $\mu = t/10, \sigma = t/3$ where $t$ is the number of points in an individual (30, in our cases.) $k$ was then constrained such that $0 < k < t$, and $k$ points were selected randomly from the individual. For each of these $k$ points, its $x$ and $y$ coordinates were shifted by a random float chosen from a Gaussian distribution with $\mu=0, \sigma=d/3$, where $d$ is the maximum possible value for $x$ or $y$, respectively, with probability {\textit indpb}. Several other methods were tried, including mutating all points with uniform probability or mutating a single point, but this didn't seem to make much difference. Additionally, increasing the mutation rate based on the standard deviation of fitnesses was attempted, but it turned out to be difficult to do properly, since the ``normal'' range of standard deviations varied considerably over different setups, and this did not seem to have a substantial effect anyway.
		\subsection{Crossover}
			Simple two-point crossover was used to combine individuals. Uniform crossover had similar results to two-point. Taking the average of points was also attempted, but had an overall detrimental effect on population fitness.
		\subsection{Population size}
			Populations of 300 and 500 were used, both with similar results.
		\subsection{Fitness evaluation}
			The company's fitness evaluation was used. Attempts to weight portions proved to be difficult and/or not helpful.
		\subsection{Selection}
			Tournament selection with three individuals was used. Selecting the $n$-best individuals or random individuals were also tested, with the former being less effective at a glance than tournament selection and the latter being, of course, random.
	\section{Results}
		Underwhelming. For the first two trials, where there are hotspots fewer than or equal to the number of towers available, the algorithm does not choose a perfect solution, or even a very good one, and we can extrapolate that it does not perform well on the latter two either. This seems to be caused by way too early convergence--the algorithm tends to get caught on a local maximum around generation sixty. \\
		Possible solutions, given more time:
		\begin{itemize}
			\item Point-by-point fitness: looking at the output of the algorithm, many of the points chosen are clearly terrible (covering no vertexes and not even near any.) Why none of the mutation algorithms used aren't improving these is unclear, but it might be helped if each point had a fitness assigned to it, so that points that are less fit might be mutated more and others less.
			\item Fitness sharing: since convergence seems to be a major issue, this would force the algorithm to play more with bad solutions.
			\item More insight: it's difficult for me to know what to do with the massive amount of data involved in analyzing the population; I just don't know how to display it in a coherent way. PyPlot can help, but I don't know how effective it is for viewing hundreds of individuals at once.
		\end{itemize}
		\subsection{Data}
			Samples were taken every twenty-five generations over four trials. By the hundredth generations, all trials had had the same max fitness for some time. \\
			\begin{tabular}{r|c|c|c|c}
			  	& 1 & 2 & 3 & 4 \\
				\hline
				0 &	-193.943&	-80.918	&	-742.434	&	-1993.540\\	
			 25 &	-59.596 &	3.009		&	-382.356	&	-888.162\\	
			 50 &	-49.122 &	10.308	&	-348.818	&	-828.045\\	
			100 &	-48.704 &	10.512	&	-348.652	&	-820.510\\	
			\end{tabular} \\
			\includegraphics[keepaspectratio, scale=0.75]{towers_graph.pdf} \\
			As this graph of the algorithm's progress on the fourth test file, the final result is reached very, very quickly, though it isn't very good.

\end{document}
    
